"""
https://leetcode.cn/problems/sort-list/description/

148. 排序链表
已解答
中等
相关标签
premium lock icon
相关企业
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

 

示例 1：


输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：


输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：

输入：head = []
输出：[]
 

提示：

链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105
 

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

"""

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
from typing import Optional
from list_node import ListNode,calc_arr,create_list_node


class Solution:
    """
    排序问题。
    在链表上处理，且链表节点属于单向节点，属于没苦硬吃。
    不需考虑效率，实现即可。

    用最易理解的归并排序实现即可。

    TODO 实在不想做了，有时间再看吧。
    """
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        root=ListNode(0,head)

        def sort_child(out_start:ListNode,mid_node:ListNode,out_end:Optional[ListNode]):
            temp1=out_start.next
            pass

        pass

if __name__=='__main__':
    pass